package binary_search;

/**题目：实现平方根函数
 *
 * @Author Gavin
 * @date 2022.01.03 10:36
 */
public class solution_1 {
    /**
     * 解题思路：
     * 一个数n的平方根的范围肯定就在0-n区间内，
     * 所以就可以使用二分搜索法来处理
     */
    //Time:O(log(n)) Space:O(1)
    public int solution(int n){
        long low=0,high=n;
        while (low<=high){
            long mid=low+(high-low)/2;
            long mid2=mid*mid;
            if(mid2<n)low=mid+1;
            else if(mid2>n)high=mid-1;
            else return (int)mid;
        }
        return (int)high;
    }
}
